package edu.cmu.cs211.proximitycounter.counter;

import java.util.*;

public class Count {
    static final int inf = 1000000;
    int n;
    Point[] a;
    
    public Count(Point[] aa)
    {
    	n = aa.length;
    	a = new Point[n];
    	for (int i=0; i<n; i++) a[i] = aa[i];
    }

    /*
     * sweep: this method counts all PAIRS of points that are within the range of r to each other in avlTree
     * 
     * The way of performing it is inserting point by point into avlTree. After each insertion, 
     * we insert all points whose y values are within the range of r into the avlTree
     * and then we do a range count on avlTree, count all elements whose x values are within the range
     * 
     * This algorithm has a running time of O(nlogn)
     */
    public int sweep (int r)
    {
    	int count = 0;
    	
    	MyTreeSet<Point> ts = new MyTreeSet<Point>();
    	int j = 0;
    	int last = 0;	// keep track of the first element whose y value is just at the boundary of the last insertion
    	
    	// loop through the array and insert element one by one
    	for (int i=0; i<n; i++)
    	{	
    		int y = a[i].getY();
    		int x = a[i].getX();
    		
    		ts = ts.insert(a[i]);
    		
    		// loop through the existing elements, delete all elements whose y values are out of range
    		for(j = last; j <= i; j++)
    		{
    			if(a[j].getY() < y-r)
    			{
    				ts = ts.delete(a[j]);		
    				last = j+1;	// keep track of the next element of the last element deleted
    			}
    		}
    		// do a rangeCount on the existing elements in the treeset, with x ranging from x-r to x+r, y from y-r to y
    		// note that the range count also counts the element itself, so we subtract 1 at the end
    		count += ts.rangeCount(new Point(x-r,y-r), new Point(x+r,y))-1;
    	}
    	return count;
    }

    public int countPairs(int r) {
    	Arrays.sort(a, Point.compy);  /* sort by increasing y value  */
		return sweep (r);
    }
}
